<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>单向链表</title>
</head>
<body>
    <script>
        //封装链表类
        function LinkedList(){
            //内部的类：节点类
            function Node(data){
                this.data = data;
                this.next = null;
            }

            //属性
            this.head = null;
            this.length = 0;

            // 1.append追加方法
            LinkedList.prototype.append = function (data){
                //创建新节点
                var newNode = new Node(data);
                //判断是否添加的是第一个节点
                if(this.length == 0){
                    //是第一个节点
                    this.head = newNode;
                }else{
                    //不是第一个节点,current是指向head，而head是指向第一个Node的，使用current指向第一个node
                    var current = this.head;
                    //依次判断current的next是否为空，直到找到next为空的node
                    while(current.next){
                        // console.log(current)
                        current = current.next;
                    }
                    //将next为空的node的next指向新加的node
                    current.next = newNode;
                }
                this.length += 1;
            }

            // 2.toString方法
            LinkedList.prototype.toString = function(){
                //定义变量
                var current = this.head;
                var listString = "";
                while(current){
                    listString += current.data + " ";
                    current = current.next;
                }
                return listString;
            }

            // 3.insert方法
            LinkedList.prototype.insert = function(position,data){
                //对position进行越界判断
                if(position < 0 || position > this.length) {return false;}

                //根据data创建newNode
                var newNode = new Node(data);
                //判断插入的位置是不是第一个
                if(position == 0){
                    newNode.next = this.head;
                    this.head = newNode;
                }else{
                    var index = 0;
                    var current = this.head;
                    var previous = null;
                    while(index++ < position){
                        previous = current;
                        current = current.next;
                    }
                    newNode.next = current;
                    previous.next = newNode;
                }

                //length
                this.length += 1;
                return true;
            }

            // 4.get方法
            LinkedList.prototype.get = function(position){
                //越界判断
                if(position < 0 || position >= this.length){ return null; }

                // 获取对应位置的data
                var current = this.head;
                var index = 0 ;
                while(index < position){
                    current = current.next;
                    index += 1;
                }
                return current.data;            
            }

            //5.indexOf方法
            LinkedList.prototype.indexOf = function(data){
                var current = this.head;
                var index = 0;
                while(current){
                    if(current.data == data){
                        return index;                        
                    }
                    current=current.next;
                    index +=1;                   
                }
                return -1;
            }

            //removeAt方法
            LinkedList.prototype.removeAt = function (position){
                if(position<0 ||position>=this.length){return false;}
                //删除的是否为第一个节点
                var current = this.head;
                if(position==0){
                    this.head = this.head.next;
                }else{
                    var index = 0;
                    // var current = this.head;
                    var previous = null;
                    while(index++ < position){
                        previous = current;
                        current = current.next;
                    }
                    //让前一个节点指向next的
                    previous.next = current.next;
                    this.length -= 1;
                    return current.data;
                }
            }

            //remove方法
            LinkedList.prototype.remove = function (data){
                var position = this.indexOf(data);
                return this.removeAt(position);
            }
            //isEmpty方法
            LinkedList.prototype.isEmpty = function(){
                return this.length == 0;
            }
            //size()方法
            LinkedList.prototype.size = function(){
                return this.length;
            }







        }


        //测试代码
        var a= new LinkedList();
        a.append('1')
        a.append('2')
        a.append('3')
        alert(a)

        a.insert(0,"aaa")
        alert(a)
        a.insert(2,"bbb")
        alert(a)
        a.insert(5,"ccc")
        alert(a)

        alert(a.get(1))
        alert(a.get(4))

        alert(a.indexOf("aaa"))




    </script>
    
</body>
</html>